//
// Created by lanlu on 2025/8/7.
//

#include <vector>
#include <iostream>
using namespace std;

// 二叉树节点结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }

    // 根节点为当前数组最大值，左右子树为当前数组最大值左右两边的子数组。
    // 递归规律为：在指定区间内查找最大值， 然后递归处理左右子数组。
    TreeNode* build(vector<int>& nums, int left, int right)
    {
        // 递归出口 left到right需要是一个有效区间
        if (left > right)
            return nullptr;

        // 在 [left,right] 范围内查找最大值索引 maxIndex
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++)
        {
            if (nums[i] > nums[maxIndex])
            {
                maxIndex = i;
            }
        }

        // TreeNode(int x) 使用初始化value的构造函数
        TreeNode * root = new TreeNode(nums[maxIndex]);
        root -> left = build(nums, left, maxIndex - 1);
        root -> right = build(nums, maxIndex + 1, right);

        return root;
    }

};